import java.util.ArrayList;



@SuppressWarnings("unchecked")
public class board implements ICellEventListener {

	public ArrayList<cell> cells = new ArrayList(81);
	public ArrayList<cell> rows[] = new ArrayList[9];
	public ArrayList<cell> cols[] = new ArrayList[9];
	public ArrayList<cell> blks[] = new ArrayList[9];
	
	private boolean _isDirty = false;
	private boolean _isSolved = false;

	public board() {
		init();
	}
	
	public board(String s) throws Exception {
		if (!(s.length() == 81 || s.length() == 243)) {throw new Exception("Input String must be 81 or 243 chars. (" + s.length() + ")");}
		// by default, all cells are unknown
		init();
		
		// setting cells by 81-char value string
		if (s.length() == 81) {
			// loop 0-80 for the string and the cells
			for (int i=0; i < 81; i++) {
				//try to cast the character to an integer.  if successful, set that cell's value.
				//  will work for values 0-9 (0=unknown)
				try {
					int x = Integer.parseInt(String.valueOf(s.charAt(i)));
					if (0 < x & x < 10) { cells.get(i).setValue(x); }
				}
				catch(Exception e) { } //do nothing, leave the cell unknown (works for non-numeric chars)
			}
		}
		else { // setting cells by 243-char state string
			// loop 0-80 for the cells
			for (int i=0; i < 81; i++) {
				//substring starts at 3*i and ends at 3*i+3
				cells.get(i).setBitmask(Integer.parseInt(s.substring(3*i,3*i+3)));
				
			}
		}
		
	}
	
	//set up the cells, rows, cols, and blks
	private void init() {
		for (int i=0; i < 9; i++) {
			rows[i] = new ArrayList<cell>();
			cols[i] = new ArrayList<cell>();
			blks[i] = new ArrayList<cell>();
		}
		
		for (int i=0; i < 81; i++) { 
			cells.add(new cell());
			//suibscribe to events
			cells.get(i).addEventListener(this);
			
			
			//add the cell to the appropriate row/col/blk
			cell thiscell = cells.get(i);
			
			int _row = -1, _col = -1, _blk = -1;
			
	    	//set row based on ID
	    	for (int j = 0; j < 9; j++) {
	    		if ( 9*j <= i && i <= (9*j)+8 ) { _row = j; }
	    	}
	    	//set column based on ID & row
	    	for (int r = 0; r < 9; r++) {
	    		for (int c = 0; c < 9; c++) {
	    			if (i == c+(9*r)) { _col = c; }
	    		}
	    	}
	    	//set block based on row and column
	    	for (int b = 0; b < 3; b++) {		
	    		if (3*b <= _col && _col < (3*b)+3 && 0 <= _row && _row < 3 ) { _blk = b; }
	    		if (3*b <= _col && _col < (3*b)+3 && 3 <= _row && _row < 6 ) { _blk = b + 3; }
	    		if (3*b <= _col && _col < (3*b)+3 && 6 <= _row && _row < 9 ) { _blk = b + 6; }
	    	}

			rows[_row].add(thiscell);
			cols[_col].add(thiscell);
			blks[_blk].add(thiscell);
		}
	}
	
	
	//get the row index for a given cell ID
	private int getRow(int cellID) {
		int val = -1;
		cell me = cells.get(cellID);
		for (int z = 0; z < 9; z++) {
			if(rows[z].contains(me)) { val = z; }
		}
		return val;
	}
	//get the column index for a given cell ID
	private int getCol(int cellID) {
		int val = -1;
		cell me = cells.get(cellID);
		for (int z = 0; z < 9; z++) {
			if(cols[z].contains(me)) { val = z; }
		}
		return val;
	}
	//get the block index for a given cell ID
	private int getBlk(int cellID) {
		int val = -1;
		cell me = cells.get(cellID);
		for (int z = 0; z < 9; z++) {
			if(blks[z].contains(me)) { val = z; }
		}
		return val;
	}
	
	private void SolveCheck() {
		//TODO:  ERROR CHECK!
		
		if (_isSolved) { return; }
		
		boolean s = true;
		for (int i = 0; i < 81; i++) {
			if (cells.get(i).getValue() == 0) { s = false; }
		}
		_isSolved = s;
		if (_isSolved) { System.out.println("Board is Solved"); }
	}
	
	public void Rule2Recursive() {

		//skip if the board is already solved
		SolveCheck();
		if (_isSolved) { return; }
		
		//avoid infinite recursion loop
		_isDirty = false;
		
		for (int i = 0; i < 9; i++) {
			Rule2(rows[i], "row", i);
			Rule2(cols[i], "col", i);
			Rule2(blks[i], "blk", i);
		}
		
		//recursion
		SolveCheck();
		if (_isSolved) { return; }
		if (_isDirty) { Rule2Recursive(); }

		Rule3Recursive();

	}
	
	public void Rule3Recursive() {

		//skip if the board is already solved
		SolveCheck();
		if (_isSolved) { return; }
		
		//avoid infinite recursion loop
		_isDirty = false;
		
		for (int i = 0; i < 9; i++) {
			Rule3(rows[i], "row", i);
			Rule3(cols[i], "col", i);
			Rule3(blks[i], "blk", i);
		}
		
		//recursion
		SolveCheck();
		if (_isSolved) { return; }
		if (_isDirty) { Rule2Recursive(); }
		Rule4Recursive();
		
	}
	
	public void Rule4Recursive() {

		//skip if the board is already solved
		SolveCheck();
		if (_isSolved) { return; }
		
		//avoid infinite recursion loop
		_isDirty = false;
		
		for (int i = 0; i < 9; i++) {
			Rule4(rows[i], "row", i);
			Rule4(cols[i], "col", i);
			Rule4(blks[i], "blk", i);
		}
		
		//recursion
		SolveCheck();
		if (_isSolved) { return; }
		if (_isDirty) { Rule2Recursive(); }
		Rule5Recursive();
	}
	
	public void Rule5Recursive() {

		//skip if the board is already solved
		SolveCheck();
		if (_isSolved) { return; }
		
		//avoid infinite recursion loop
		_isDirty = false;
		
		for (int i = 0; i < 9; i++) {
			Rule5(rows[i], "row", i);
			Rule5(cols[i], "col", i);
			Rule5(blks[i], "blk", i);
		}
		
		//recursion
		SolveCheck();
		if (_isSolved) { return; }
		if (_isDirty) { Rule2Recursive(); }
		Rule6Recursive();
	}
	
	public void Rule6Recursive() {
		//skip if the board is already solved
		SolveCheck();
		if (_isSolved) { return; }
		
		//avoid infinite recursion loop
		_isDirty = false;
		
		for (int i = 0; i < 9; i++) {
			Rule6(blks[i]);
		}
		
		//recursion
		SolveCheck();
		if (_isSolved) { return; }
		if (_isDirty) { Rule2Recursive(); }
		Rule7Recursive();
	}
	
	public void Rule7Recursive() {
		//skip if the board is already solved
		SolveCheck();
		if (_isSolved) { return; }
		
		//avoid infinite recursion loop
		_isDirty = false;
		
		for (int i = 0; i < 9; i++) {
			Rule7(rows[i], "row", i);
			Rule7(cols[i], "col", i);
			Rule7(blks[i], "blk", i);
		}
		
		//recursion
		SolveCheck();
		if (_isSolved) { return; }
		if (_isDirty) { Rule2Recursive(); }
		Rule8Recursive();
	}
	
	public void Rule8Recursive() {
		//skip if the board is already solved
		SolveCheck();
		if (_isSolved) { return; }
		
		//avoid infinite recursion loop
		_isDirty = false;
		
		for (int i = 0; i < 9; i++) {
			Rule8(rows[i], "row", i);
			Rule8(cols[i], "col", i);
			Rule8(blks[i], "blk", i);
		}
		
		//recursion
		SolveCheck();
		if (_isSolved) { return; }
		if (_isDirty) { Rule2Recursive(); }
	}
	
	
	
	
	//RULE #1: if a cell has only one possible value x, then that cell value is = x
	//			this rule is handled automatically by the cell class through the use of bitmasks
	
	//RULE #2: if a known value(x) appears in a group(g), then all other cells in (g) cannot be (x)
	private void Rule2(ArrayList<cell> group, String type, int groupid) {
		//outer loop: cells in the group
		for (cell x : group) {
			int val = x.getValue();
			if (val == 0) { continue; } // continue loop if this cell is not known
				// inner loop:  other cells in the group
				for (cell y : group) {
					if( (!(x == y)) && (y.isBitSet(val)) ) { //don't apply rule on same cell, or if val is already cleared
							y.clearBit(val);
							System.out.println("Rule2 applied for " + type + "(" + groupid + ") cell(" + group.indexOf(y) + ") Value(" + val + ").");
					}
				}
		}
	}
	
	//RULE #3: if a possible value (x) appears only once in a group(g) then that cell's value must be (x).
	private void Rule3(ArrayList<cell> group, String type, int groupid) {
			// outer loop: values 1-9
			for (int val=1; val < 10; val++) {
				int count = 0, id = -1; //reset count and cell number
				boolean escape = false;
				// inner loop:  cells in the group
				for (cell x : group) {
					
					if (x.getValue() == val) { escape = true; } //escape this value if already known
					if ( x.isBitSet(val) ) { 
						count++;
						id = group.indexOf(x);
					}
				}
				// if occurences = 1 then find that cell and apply Rule3
				if ( (count == 1) && (!(escape)) ) { group.get(id).setValue(val); 
					System.out.println("Rule3 applied for " + type + "(" + groupid + ") cell(" + id + ") Value(" + val + ").");
				}
			}
		
	}
	
	//RULE #4: NAKED PAIRS/TRIPS/QUADS/etc. if (n) cells share the same (n) possibilities {v} in a group(g), 
	//			then all other cells in (g) cannot be {v}.
	private void Rule4(ArrayList<cell> group, String type, int groupid) {
		for (cell x : group) {
			if (x.getValue() > 0) { continue; }
			
			//TODO:  can redo this like rule 5
			//count the number of bits set
			int bcount = 0;
			for (int i = 1; i < 10; i++) { if (x.isBitSet(i)) { bcount++; }}
			
			//create an array of cells with same bitmask value
			int bval = x.getBitmask();
			ArrayList<cell> bucket = new ArrayList<cell>(1);
			bucket.add(x);
			for (cell y : group) {
				if ( (!(y == x)) && (y.getBitmask() == bval) ) { bucket.add(y);	}
			}
			
			//count cells in bucket and compare to bit count
			if (bucket.size() == bcount) {
				//for all cells not in the bucket...
				for (cell z : group) {
					if ( (!(bucket.contains(z)) && (((z.getBitmask() & bval) == bval)) ) ) {
						//clear the bval from the cell's bitmask
						z.setBitmask(z.getBitmask() & ~bval);
						System.out.println("Rule4 applied for " + type + "(" + groupid + ") cell(" + group.indexOf(z) + ") bitmaskValue(" + bval + ").");
					}
				}	
			}	
		}
	}
	
	//RULE #5: if (n) cells share any combination of (n) possibilities {v} in a group, then all other cells in (g) cannot be {v}.
	public void Rule5(ArrayList<cell> group, String type, int groupid) {
		
		for (cell x : group) { //outer loop: first cell
			if (x.getValue() > 0) { continue; }
			ArrayList<cell> bucket = new ArrayList<cell>(1);
			bucket.add(x);
			//System.out.println("starting cell: " + group.indexOf(x));
			//now find cells with simialr or subsetted bitmasks by using bitwise inclusive OR
			for (cell y : group) {
				if ( (y.getValue() > 0) || (y == x) ) { continue; }
				if ( (int)(y.getBitmask() | x.getBitmask()) == x.getBitmask() ) {
					bucket.add(y);
					//System.out.println("\tadding cell: " + group.indexOf(y));
				}
			}
			//bucket must contain at least 3 cells to satisfy this condition (even though cells which satisfy rule 4 would work too)
			if (bucket.size() < 3) { continue; }
			
			//find max number of bits represented in the bucket
			int mask = 0;
			for (cell z : bucket) {
				mask = mask | z.getBitmask();
			}
			int bitcount = Integer.bitCount(mask);
			
			//max number of bits set across all cells must equal number of cells in bucket.
			if ( !(bucket.size() == bitcount) ) { continue; }
				
			
			System.out.print("Rule5: " + type + "(" + groupid + "): possible group: ");
			for (cell z : bucket) { System.out.print(group.indexOf(z) + " "); }
			System.out.print("\n");
			
			
			//for all cells not in the bucket...
			for (cell z : group) {
				//if ( (!(bucket.contains(z)) && (((z.getBitmask() & mask) == mask)) ) ) {
				if ( (!(bucket.contains(z))) && (z.getValue() == 0)   ) {
					//clear the mask from the cell's bitmask
					z.setBitmask(z.getBitmask() & ~mask);
					System.out.println("Rule5 applied for " + type + "(" + groupid + ") cell(" + group.indexOf(z) + ") bitmaskValue(" + mask + ").");
				}
			}
				
			
			
		}
		
		
	}
	
	
	
	
	//RULE #6: if, in a given block (b), a given value (x) is only possible in a single row or column within (b),
	//			then all other cells in the same row or column OUTSIDE of (b) cannot be (x)
	private void Rule6(ArrayList<cell> block) {
		
		//loop through each value
		for (int val = 1; val < 10; val++) {
			
			//create a bucket of cells in this block that have the possible value
			ArrayList<cell> bucket = new ArrayList<cell>(1);
			for (cell x : block) { if (x.isBitSet(val)) { bucket.add(x); } }
			//escape if not 2 or 3 cells in bucket
			if ( (bucket.size() < 2) || (bucket.size() > 3) ) { continue; }
			
			// ** ROW CHECK **
			//if all cells in the bucket(this block) have the same row then other cells in the row cannot have this value
			int r0 = -1, r1 = -1, r2 = -1;
			//get the rows of the first 2 bucket cells
			r0 = getRow(cells.indexOf(bucket.get(0)));
			r1 = getRow(cells.indexOf(bucket.get(1)));
			//if there's a third bucket cell, get its row
			if (bucket.size() == 3) { r2 = getRow(cells.indexOf(bucket.get(2))); }
			if (!(r0 == r1)) { continue; } //escape if the 1st and 2nd cell are not in the same row
			if (!(r2 == -1)) { //if there is a 3rd cell in the bucket
				if (!(r0 == r2)) { continue; } //escape if the 3rd cell is not in the same row
			}
			//if got this far, then r0,r1, and possibly r2 all contain the absolute row number to clear bits,
			//  while bucket contains the cells we don't want to clear (inside this block)
			for (cell y : rows[r0]) {  //for all cells in this row...
				if ( bucket.contains(y) ) { continue; }  //escape if the cell is in the bucket
				if ( y.isBitSet(val) ) {  //if the bit is set for the outside cells, apply the rule
					y.clearBit(val);
					System.out.println("Rule6 applied for row(" + r0 + ") cell(" + rows[r0].indexOf(y) + ") Value(" + val + ")." );
				}
			}
	
		}
		
		
		//loop through each value
		for (int val = 1; val < 10; val++) {
			
			//create a bucket of cells in this block that have the possible value
			ArrayList<cell> bucket = new ArrayList<cell>(1);
			for (cell x : block) { if (x.isBitSet(val)) { bucket.add(x); } }
			//escape if not 2 or 3 cells in bucket
			if ( (bucket.size() < 2) || (bucket.size() > 3) ) { continue; }
			// ** COL CHECK **
			//if all cells in the bucket(this block) have the same col then other cells in the col cannot have this value
			int c0 = -1, c1 = -1, c2 = -1;
			//get the cols of the first 2 bucket cells
			c0 = getCol(cells.indexOf(bucket.get(0)));
			c1 = getCol(cells.indexOf(bucket.get(1)));
			//if there's a third bucket cell, get its col
			if (bucket.size() == 3) { c2 = getCol(cells.indexOf(bucket.get(2))); }
			if (!(c0 == c1)) { continue; } //escape if the 1st and 2nd cell are not in the same col
			if (!(c2 == -1)) { //if there is a 3rd cell in the bucket
				if (!(c0 == c2)) { continue; } //escape if the 3rd cell is not in the same col
			}
			//if got this far, then c0,c1, and possibly c2 all contain the absolute col number to clear bits,
			//  while bucket contains the cells we don't want to clear (inside this block)
			for (cell y : cols[c0]) {  //for all cells in this col...
				if ( bucket.contains(y) ) { continue; }  //escape if the cell is in the bucket
				if ( y.isBitSet(val) ) {  //if the bit is set for the outside cells, apply the rule
					y.clearBit(val);
					System.out.println("Rule6 applied for col(" + c0 + ") cell(" + cols[c0].indexOf(y) + ") Value(" + val + ")." );
				}
			}
		}
		
	}
	
	//RULE #7:  HIDDEN PAIRS:  if in a given group, there are 2 values that only appear in the same 2 cells,
	//			then those two cells cannot contain any other values
	public void Rule7(ArrayList<cell> group, String type, int groupid) {
		
		for (int val1 = 1; val1 < 10; val1++) {
			for (int val2 = 1; val2 < 10; val2++) {
				if (val2 == val1) { continue; }
				ArrayList<cell> bucket = new ArrayList<cell>(1);
				
				for (cell x : group) {
					if (x.getValue() > 0) { continue; }
					if ( (x.isBitSet(val1)) && (x.isBitSet(val2)) && ( (x.getBitCount() <= 3) ) ) { 
						bucket.add(x); 
					}
				}
				if (!(bucket.size() == 2)) { continue; }
				
				for (cell z: bucket) {
					for (int v = 1; v < 10; v++) {
						if ( (!(v == val1)) && (!(v == val2)) && (z.isBitSet(v)) ) {
							z.clearBit(v);
							System.out.println("Rule7 applied for " + type + "(" + groupid + ") cells(" + 
									group.indexOf(bucket.get(0)) + "," + group.indexOf(bucket.get(1)) +
									") Values(" + val1 + "," + val2 + ").  Cell(" + group.indexOf(z) + ") " +
									"cannot be " + v);
						}
					}
				}
			}
		}
		
		//outer loop: value 1
//		for (int val1 = 1; val1 < 10; val1++) {
//			
//			ArrayList<cell> bucket1 = new ArrayList<cell>(1);
//			
//			
//			for (cell x : group) {
//				if (x.getValue() > 0) { continue; }
//				if (x.isBitSet(val1)) { bucket1.add(x); }
//			}
//			if (!(bucket1.size() == 2)) { continue; }
//			
//			
//			//inner loop: value 2
//			for (int val2 = 1; val2 < 10; val2++) {
//				if (val2 == val1) { continue; }
//				ArrayList<cell> bucket2 = new ArrayList<cell>(1);
//				
//				for (cell y : group) {
//					if (y.getValue() > 0) { continue; }
//					if (y.isBitSet(val2)) { bucket2.add(y); }
//				}
//				
//				if (!(bucket2.size() == 2)) { continue; }
//				
//				if ( (bucket1.get(0).equals(bucket2.get(0))) && (bucket1.get(1).equals(bucket2.get(1))) ) {
//					//the two buckets match, a hidden pair is found
//					for (cell z: bucket1) {
//						
//						for (int v = 1; v < 10; v++) {
//							
//							
//							
//							if ( (!(v == val1)) && (!(v == val2)) && (z.isBitSet(v)) ) {
//								z.clearBit(v);
//								System.out.println("Rule7 applied for " + type + "(" + groupid + ") cells(" + 
//										group.indexOf(bucket1.get(0)) + "," + group.indexOf(bucket1.get(1)) +
//										") Values(" + val1 + "," + val2 + ").");
//							}
//						}
//										
//
//					}
//
//				}
//			}
//		}
	}
	
	//RULE #7:  HIDDEN TRIPS:  if in a given group, there are 3 values that only appear in the same 3 cells,
	//			then those three cells cannot contain any other values
	public void Rule8(ArrayList<cell> group, String type, int groupid) {
		for (int val1 = 1; val1 < 10; val1++){
			for (int val2 = 1; val2 < 10; val2++) {
				if (val2 == val1) { continue; }
				for (int val3 = 1; val3 < 10; val3++) {
					if ( (val3 == val1) || (val3 == val2) ) { continue; }
					
					ArrayList<cell> bucket = new ArrayList<cell>(1);
					
					for (cell x : group) {
						if (x.getValue() > 0) { continue; }
						if ( (x.isBitSet(val1)) && (x.isBitSet(val2)) && (x.isBitSet(val3)) && 
								( (x.getBitCount() == 3) || (x.getBitCount() == 4) ) ) { 
							bucket.add(x); 
						}
					}
					if (!(bucket.size() == 3)) { continue; }
					
					for (cell z: bucket) {
						for (int v = 1; v < 10; v++) {
							if ( (!(v == val1)) && (!(v == val2)) && (!(v == val3)) && (z.isBitSet(v)) ) {
								z.clearBit(v);
								System.out.println("Rule7 applied for " + type + "(" + groupid + ") cells(" + 
										group.indexOf(bucket.get(0)) + "," + group.indexOf(bucket.get(1)) +
										") Values(" + val1 + "," + val2 + "," + val3 + ").  Cell(" + group.indexOf(z) + ") " +
										"cannot be " + v);
							}
						}
					}
					
					
				} //val3
			} //val2
		} //val1
		
		
		
		
//		for (int val1 = 1; val1 < 10; val1++) {
//			for (int val2 = 1; val2 < 10; val2++) {
//				if (val2 == val1) { continue; }
//				ArrayList<cell> bucket = new ArrayList<cell>(1);
//				
//				for (cell x : group) {
//					if (x.getValue() > 0) { continue; }
//					if ( (x.isBitSet(val1)) && (x.isBitSet(val2)) && ( (x.getBitCount() == 2) || (x.getBitCount() == 3) ) ) { 
//						bucket.add(x); 
//					}
//				}
//				if (!(bucket.size() == 2)) { continue; }
//				
//				for (cell z: bucket) {
//					for (int v = 1; v < 10; v++) {
//						if ( (!(v == val1)) && (!(v == val2)) && (z.isBitSet(v)) ) {
//							z.clearBit(v);
//							System.out.println("Rule7 applied for " + type + "(" + groupid + ") cells(" + 
//									group.indexOf(bucket.get(0)) + "," + group.indexOf(bucket.get(1)) +
//									") Values(" + val1 + "," + val2 + ").  Cell(" + group.indexOf(z) + ") " +
//									"cannot be " + v);
//						}
//					}
//				}
//			}
//		}
	}
	
	
	
	public void handleEventCellBitmaskChanged(cell e) {
		//System.out.println("EventCellBitmaskChanged: " + e.getValue() + ":" + e.toString());
		_isDirty = true;
	}

	public void handleEventCellisSolved(cell e) {
		_isDirty = true;
	}

	public void handleEventCellValueChanged(cell e) {
		//System.out.println("EventCellValueChanged:   " + e.getValue() + ":" + e.toString());
		_isDirty = true;
	}


	
}
